The advent of virtualization technologies for commodity hardware has provided benefits with respect to managing large-scale computing resources for many customers with diverse needs, allowing various computing resources to be efficiently and securely shared by multiple customers. For example, virtualization technologies may allow a single physical computing machine to be shared among multiple users by providing each user with one or more virtual machines hosted by the single physical computing machine, with each such virtual machine being a software simulation acting as a distinct logical computing system that provides users with the illusion that they are the sole operators and administrators of a given hardware computing resource, while also providing application isolation and security among the various virtual machines. Furthermore, some virtualization technologies are capable of providing virtual resources that span two or more physical resources, such as a single virtual machine with multiple virtual processors that spans multiple distinct physical computing systems. As another example, virtualization technologies may allow data storage hardware to be shared among multiple users by providing each user with a virtualized data store (e.g., a database) which may be distributed across multiple data storage devices, with each such virtualized data store acting as a distinct logical data store that provides users with the illusion that they are the sole operators and administrators of the data storage resource.
In many environments, operators of provider networks that implement different types of virtualized computing, storage, and/or other network-accessible functionality allow customers to reserve or purchase access to resources in any of several different resource acquisition modes. For example, a customer may reserve a virtual compute resource instance for a relatively long duration, such as one year or three years, or a customer may purchase resources for shorter terms on an ad-hoc basis as needed. For some types of resource reservations, at least a portion of the price paid by the customer may fluctuate over time in response to changing demand and supply of the resources within the provider network. The provider network operator may have to try to ensure that a number of potentially competing demands are met, e.g., that all guaranteed commitments to clients (such as long-term reservations that have already been paid for) are honored, that the dynamically-varying component of resource pricing does not get so high that customer satisfaction suffers, that the provider's data center investment is justified by a reasonable level of resource utilization and revenue, and so on. In business environments where clients may choose from among multiple providers for network-based computing options, provider network operators may wish to maintain high levels of customer satisfaction and customer retention, e.g., by making resource acquisition easy and economical, and by reducing the complexity of client resource budget management as much as possible. The service provider must also balance the competing goals of providing high durability and/or availability (e.g., in the face of node or network failures) while avoiding situations in which large numbers of redundant resource instances that are provisioned to provide durability and/or availability to clients lay idle most, if not all, of the time.
One type of network-based service that is offered to clients is a database service. While distribution of various components of a software stack can in some cases provide (or support) fault tolerance (e.g., through replication), higher durability, and less expensive solutions (e.g., through the use of many smaller, less-expensive components rather than fewer large, expensive components), databases have historically been among the components of the software stack that are least amenable to distribution. For example, it can be difficult to distribute databases while still ensuring the so-called ACID properties (e.g., Atomicity, Consistency, Isolation, and Durability) that they are expected to provide. In traditional database systems, the data managed by a database system is stored on direct attached disks. If a disk fails, it is replaced and then must be reloaded with the appropriate data. For example, in many systems, crash recovery includes restoring the most recent snapshot from a backup system and then replaying any changes made since the last snapshot from that point forward. However, this approach does not scale well to large databases. In addition, in order to recover quickly from a crash, such systems often must provision redundant hardware, software, and/or network resources (at considerable expense) that are rarely, if ever, used.
While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). Similarly, the words “include,” “including,” and “includes” mean including, but not limited to.